/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package edu.pw.elka.gtsna.centrality.betweenness;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

import edu.pw.elka.gtsna.centrality.NodeCentrality;
import edu.pw.elka.gtsna.graph.Graph;

/**
 *
 * @author Piotr Szczepanski
 * The framework for Brandes algorithm
 * All algorithms works in O(nm) time, where n is number of vertices and m number of edges.
 */

public class NodeBetweennessCentrality extends NodeCentrality {

    Queue<Integer> queue; 
    Stack<Integer> stack;
    Map<Integer, Double> dist;
    Map<Integer,List<Integer>> pred;
    Map<Integer,Integer> sigma;
    Map<Integer,Double> delta;
    
    public NodeBetweennessCentrality(Graph graph) {
    	super(graph);
        stack = new Stack<Integer>();
        dist = new HashMap<Integer,Double>();
        pred = new HashMap<Integer,List<Integer>>();
        sigma = new HashMap<Integer,Integer>();
        delta = new HashMap<Integer,Double>();
        queue = new LinkedList<Integer>();
    }
   
    protected double getDistance(int node){
    	return dist.get(node);
    }
    
    protected int getSigma(int node){
    	return sigma.get(node);
    }
    
    protected double getDelta(int node){
    	return delta.get(node);
    }

    void singleSourceShortestPath(int source){
        dist.put(source, 1.0);
        sigma.put(source, 1);
        queue.offer(source);
    	
        while (!queue.isEmpty()) {
        	Integer v = queue.poll();
            stack.push(v);
            for(Integer w: graph.getNeigbours(v)){
                if (dist.get(w) == Double.MAX_VALUE ) {
                    dist.put(w, dist.get(v) + 1);
                    queue.offer(w);
                }
                if (dist.get(w) == dist.get(v) + 1) {
                    sigma.put(w, sigma.get(w) + sigma.get(v));
                    pred.get(w).add(v);
                }
            }
        }
    }
    

    void accumulation(int source) {
        while (!stack.isEmpty()){
        	Integer w = stack.pop();
            for(Integer v: pred.get(w)){
                delta.put(v, delta.get(v) + ((sigma.get(v).doubleValue()*(1.0 + delta.get(w)))/sigma.get(w).doubleValue()));
            }
            if (!w.equals(source)) {
            	centralities.put(w, centralities.get(w)+(delta.get(w)/2.0));
            }
        }
    }
    

    
    void initialization(){
        for (Integer vert: graph.getAllNodes()) {
            pred.put(vert, new LinkedList<Integer>());
            dist.put(vert, Double.MAX_VALUE);
            sigma.put(vert, 0);
            delta.put(vert, 0.0);            
        }
    }
    
    
    public void computeCentrality(){
        for (Integer vertex: graph.getAllNodes()){
            centralities.put(vertex, 0.0);
        }   
        for (Integer source: graph.getAllNodes()) {
        	computeSourceInfluecnes(source);    
        }

    }

    public void computeSourceInfluecnes(int source){
    	initialization();
        singleSourceShortestPath(source);           
        accumulation(source);
    }
    
    public Graph getGraph() {
        return graph;
    }

    public void setGraph(Graph graph) {
        this.graph = graph;
    }
    

     
       
}


